#include <iostream>
using namespace std;

int jump(int A[], int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(n<2){
		return 0;
	}
	int *jump = new int[n];
	jump[0] = 0;
	for(int i=1; i<n; ++i){

		
		jump[i] = 0x7FFFFFFF;
		for(int j=i-1; j>=0; --j){
			if((j + A[j] >= i) 
				&& (jump[j]+1 < jump[i])){
				jump[i] = jump[j] + 1;
			}
		}
	}
	int res = jump[n-1];
	delete []jump;

	return res;
}

int jump1(int A[], int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(n<2){
		return 0;
	}
	
	int curIndex = 0;
	int tarIndex = A[0];
	int backIndex = 1;
	int layer = 1;
	while(1){
		if(tarIndex >= n-1){
			break;
		}
		// find max within [curIndex+1, tarIndex]
		int far = tarIndex+A[tarIndex];
		int fari = tarIndex;
		for(int i=backIndex; i<tarIndex; ++i){
			if(i+A[i] > far){
				far = i+A[i];
				fari = i;
			}
		}
		// jump to far index
		curIndex = fari;
		backIndex = tarIndex;
		tarIndex = curIndex + A[curIndex];
		++layer;
		
	}
	return layer;
}



int main(){

	int a[] = {7,0,9,6,9,6,1,7,9,0,1,2,9,0,3};
	cout<<jump1(a, sizeof(a)/sizeof(a[0]));
	return 0;
}